package algorithm.leetcode.I1to100;

/**
 * 在一个含重复元素的旋转数组中查找是否包含某个值
 * 和 Q33 差不多,注意几个大于等于和小于等于号的位置,很重要
 */

public class Q81 {

    public boolean search(int[] nums, int target) {
        int low = 0, high = nums.length-1;

        while (low <= high) {
            int mid = ((high-low)>>1) + low;

            // 如果while中允许low==high这一情况,则必须在循环内安排return true
            if (nums[mid] == target) return true;

            // 这是一种特殊情况,头尾中都相等并且还不是目标值,就把两边界各自向内收缩
            if (nums[mid] == nums[high] && nums[mid] == nums[low]) {
                high--;
                low++;
            }
            // 右侧有序
            else if (nums[mid] <= nums[high]) {
                // 在右边,去右边找
                if (nums[mid] < target && target <= nums[high]) low = mid+1;
                // 不然就在左边,去左边找
                else high = mid-1;
            }
            // 左侧有序
            else {
                // 在左边,去左边找
                if (nums[low] <= target && target < nums[mid]) high = mid-1;
                // 不然就在右边找
                else low = mid+1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Q81 q81 = new Q81();
        System.out.println(q81.search(new int[]{3,1}, 1));
        System.out.println(q81.search(new int[]{1,0,1,1,1}, 1));
        System.out.println(q81.search(new int[]{1,0,1,1,1}, 0));
        System.out.println(q81.search(new int[]{1}, 1));
        System.out.println(q81.search(new int[]{2}, 1));
        System.out.println(q81.search(new int[]{1,1,1,1,1,1,1,1,1,13,1,1,1,1,1,1,1,1,1,1,1,1}, 13));
    }
}
